package Work;

import java.util.Arrays;

//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
//https://leetcode.cn/problems/majority-element/
public class test4 {
    public static void main(String[] args) {
//        int[] array={1,3,2,6,8,8,8,8,8};
//        Arrays.sort(array);
//        System.out.println(array[array.length/2]);

        //方法2：摩尔投票法
        int[] array={1,3,2,6,8,8,8};
        System.out.println(majorityElement(array));
    }

    public static int majorityElement(int[] array) {
        int major = array[0];
        int count = 0;
        int length = array.length;
        for(int i = 0; i < length; i++) {
            if(major == array[i]) {
                count++;
            }
            else {
                count--;
            }

            if(count == 0) {
                major = array[i];
                count = 1;
            }
        }
        return major;
    }
}
